Serial data communication has become very common over the last several years in various industries, including business, commercial, and telecommunications to name a few. In order to communicate more information, often such information is multiplexed onto the media for transmission, and demultiplexed at the receiving end of the media. Thus, the receiving end requires some type of method and/or mechanism for synchronizing the information so that it may be properly demultiplexed into its original constituent parts. The present invention provides an improved method and apparatus in this regard.
FIG. 1 illustrates a prior art data frame of serial bits denoted generally at 10. Data frames are known in the art as packets of bits which are serially communicated from one point to another. Data frame 10 is illustrated as having several rows evenly numbered 12 through 24. Rows 12 through 24 by convention demonstrate that one row is serially communicated followed by the next and so on. Communication of the serial bits may be from right to left or left to right for a row, and may be further broken down by bytes or groups within the frame. Either the least or most significant bit of a byte or group may be communicated first when transmitting a byte or group.
As known in the art, the beginning and end of data frames are typically defined relative to some type of delimiting characteristic(s). Particularly, the delimiting characteristic is typically interspersed throughout the data frame. Thus, by identifying the delimiting characteristics of data frame 10, a system may determine the location of the beginning and end of the frame, as well as the location of any pre-specified information between its beginning and end. Such location techniques are commonly used to synchronize receipt of a data frame, or distinguish it from previously, or subsequently, received data frames.
The delimiting characteristics of a data frame may be established in many ways, and may be dictated by industry or application-specific standards. For example, each row 12 through 24 of data frame 10 includes a framing pattern sequence which consists of four specified bits located at fixed locations within each frame row. For illustration purposes, each fixed bit location for each row is successively labeled with reference characters "a", "b", "c", and "d." Thus, row 12 includes fixed bit locations 12a, 12b, 12c, and 12d, where each location stores a specified identifier bit. Rows 14 through 24 likewise include such fixed bit locations for containing similar frame identifier bits. Note that each fixed bit location is spaced apart a known number of locations from other bits. Typically, although not necessarily, the known number is constant, so that the identifier bits are periodically spaced within a frame. Therefore, and as detailed below, the format of data frame 10 permits a system to identify four evenly-spaced bits in a row and, if those bits match a pre-specified framing pattern, the beginning and end of data frame 10 may be located by knowing the distance between the bit pattern and the frame beginning and end. Although not shown, another type of delimiting characteristic, that is, another method of locating identifier bits, is fixing bit locations solely at the beginning of row 12 and the end of row 24. Still other types of delimiting characteristics are known, apparent, or will become apparent, to persons skilled in the art.
FIG. 2 illustrates a flow chart of a prior art method of searching a data frame, such as data frame 10 of FIG. 1, to locate the framing pattern and, thereby, determine the proper alignment of the frame. In general, the method arbitrarily chooses a given bit as a first candidate bit of the correct framing pattern. It thereafter examines enough periodically spaced bits after the first arbitrary bit to determine if the examined bits in their entirety are the proper framing pattern. If the assumed bits match the framing pattern, the beginning and end of the frame may be defined for synchronization or other purposes. If the assumed bits are not the proper framing pattern, a different first candidate bit is again assumed to be the first bit of the correct framing pattern and it, along with subsequent periodic bits, are examined. The method repeats until the proper framing pattern sequence is located. The specific steps of the prior art method are described below.
The method of FIG. 2 examines bits which are periodically spaced N bits apart in the serial data stream under consideration and, again, examines those bits under the assumption that they represent the correct framing pattern. In the example of FIG. 2, the method searches for a framing pattern used in the telecommunications industry for the framing pattern in a DS3 data frame. As known, the DS3 framing pattern consists of four bits, namely, 1001. Each bit is spaced 170 bit times from another framing bit. Note that the four bit pattern may begin anywhere within the sequence of these four bits, and therefore is valid as 1001, 0011, 0110, or 1100. Moreover, as discussed in connection with the following Table 1, at least three bits must be analyzed to determine if the assumed bit sequence is the proper framing pattern.
TABLE 1 ______________________________________ Possible Possibly Case sequence Valid? ______________________________________ 1 0 0 0 No 2 0 0 1 Yes 3 0 1 0 No 4 0 1 1 Yes 5 1 0 0 Yes 6 1 0 1 No 7 1 1 0 Yes 8 1 1 1 No ______________________________________
Table 1 illustrates the eight (i.e., 2.sup.3 =8) cases of possible bit sequences which may be incurred when examining three bits. Moreover, Table 1 illustrates that four cases (i.e., cases 2, 4, 5, and 7) of the overall eight cases represent sequences which might indicate a valid framing pattern. In other words, if any of cases 2, 4, 5, or 7 are incurred, then the method must await a fourth bit to determine if the proper framing pattern has been detected. To the contrary, however, if any of cases 1, 3, 6, or 8 are incurred in the examining method, the method may conclude that it has not located the proper framing pattern and, thus, must choose an alternative set of bits in another effort to locate that pattern. Thus, given a method which examines bits to locate the pattern of 1001, at least three bits must be examined before any pattern can be disregarded as an invalid pattern.
Note also that the above describes detecting a single occurrence of the correct pattern, namely, four bits in the appropriate sequence as given. In actual operation, it is possible that the four bits might inadvertently occur in proper sequence even though the correct pattern has not been located. Accordingly, it is known in the art to ensure that the pattern itself repeats numerous times to ensure correct identification. For example, for a four bit pattern, it has been empirically determined that the entire pattern should be detected three consecutive times before it is concluded that in fact the correct pattern has been located. Thus, so long as the tested bits continue to be valid, a total of twelve bits are analyzed to ensure three successive arrivals of the proper framing pattern.
Having described some general principles involved in frame pattern recognition, reference is made to FIG. 2 wherein a prior art method of identifying proper frame pattern sequences is described. Beginning in step 26, a first candidate bit is identified at an arbitrary first location, LOC.sub.X. This bit may be copied in a register or some other type of storage type device for subsequent evaluation. For example, a state machine could be used in lieu of a register, where the state of operation is representative of the previous bit or bits. Step 28 skips N-1 bits using a counter as the N1 bits are serially received. Step 30 identifies a second candidate bit at a location LOC.sub.X+N, where the subscript X+N indicates that the second candidate bit is N bits after the first candidate bit identified in step 26. Like the first candidate bit, the second candidate bit may be copied in a register or the like for subsequent evaluation. Next, step 32, like step 28, skips N-1 bits, these N-1 bits following the second candidate bit at LOC.sub.X+N.
Step 34 identifies a third candidate bit at a location, LOC.sub.X+2N, and this third candidate bit is also stored in a register or the like. Having stored three bits, the method continues with step 36 wherein a first comparison is performed. Specifically, step 36 determines whether the three stored bits (from locations LOC.sub.X, LOC.sub.X+N, and LOC.sub.X+2N) represent a valid portion of a framing pattern. If a valid pattern portion is detected, the method continues to step 37 which, as described below, continues the flow to determine if subsequent bits are likewise valid for a given framing pattern. If, however, a valid pattern is not detected, the method continues to step 40 which, as described below, creates an adjustment to begin the method over until the correct framing pattern is located. Thus, in the example of Table 1, the three candidate bits are compared to each of the eight cases shown therein. If the bits follow any of cases 2, 4, 5, or 7, the method continues to step 37; to the contrary, if the bits follow any of cases 1, 3, 6, or 8, the method continues to step 40.
As described above, if the process reaches step 37, then the bits encountered thus far represent a valid portion of the framing pattern in question, and the process continues to determine if a successive bit(s) continues to represent a valid pattern. In particular, step 37 establishes a count of valid bits incurred thus far. For purposes of example, the count is named "VALID CNT", indicating the total count of successive matching candidate bits. Next, step 38, like steps 28 and 32, skips N-1 bits. Moreover, step 42, like steps 26, 30, and 34, identifies yet another candidate bit, namely, a fourth candidate bit at a location, LOC.sub.X+3N, where the subscript X+3N indicates that the fourth bit is 3*N bits after the first candidate bit identified in step 26.
Step 44, in a manner similar to step 36, determines if the now-accumulated four candidate bits represent a valid framing pattern. If the four bits represent a valid pattern, the method continues to step 45a which, as mentioned above, begins the determination of whether the pattern of four bits has arrived three successive times. Particularly, step 45a determines if the number of valid successive candidate bits (i.e., VALID CNT) exceeds twelve; if not, the method continues to step 45b which increments the count of successive candidate bits. Thereafter, steps 38, 42, 44, 45a, and 45b repeat until twelve valid successive candidate bits are identified. Of course, if an invalid candidate bit is incurred during the additional repetitions, then step 44 detects this occurrence and returns the method to step 40 as described above. On the other hand, if twelve valid successive candidate bits are incurred, the method continues to step 46 where a signal is issued identifying that the correct framing pattern within the serial data has been located and detected. Accordingly, in step 48 the method stops, having achieved its purpose. As discussed above, once the framing pattern is identified (as represented by the signal of step 46), dependent functions such as frame synchronization may be implemented.
Returning to step 44, note that the method continues to step 40 if the four candidate bits do not match the desired framing pattern. Additionally, as mentioned with reference to step 36, the method also continues to step 40 if the portion of candidate bits (three in example described) do not match any portion of the desired framing pattern. In either case, having reached step 40, it is recognized that the initially assumed location, LOC.sub.X, was an inaccurate location for the first candidate bit in the framing pattern sequence. In the prior art method shown, the method then recommences to find a sequence of three new candidate bits, first by assuming a new location for the new "first" candidate bit. Particularly, in step 40, the method "slips" one bit, meaning, it skips to the next successive bit following the last identified candidate bit. In the prior art, this step is controlled by a state machine which causes the slip and then recommences the method with step 26. Accordingly, the "first" bit of the next three candidates is identified at a new location X which, because of the one bit slip, is the bit immediately following the last of the candidate bits in the previous sequence. For example, if step 40 were reached from a mismatch in step 36, then bits at locations LOC.sub.X, LOC.sub.X+2N, and LOC.sub.X+3N were the previous candidate bits. Thus, once step 40 slips to the next bit, the "first" candidate bit identified in the subsequent step 26 is actually at the location LOC.sub.X+3N+1. Accordingly, as the method continues to step 30, the next identified bit is at location LOC.sub.X+4N+1, and so forth.
From the above, note that the method of FIG. 2 continues until a valid framing pattern is identified. Moreover, note that each time an assumed pattern is determined to be invalid, the entire process repeats. In the prior art, this wait time is governed by the above-mentioned state machine which forces at least steps 26 through 36 to occur for each set of candidate bits. Because at least three candidate bits must be accumulated for each repetition of these steps, the method requires at least 2N bits to pass (i.e., the time necessary to accumulate three candidate bits) before the next determination can be made as to whether a valid pattern is detected. Recall, in the DS3 example described above, N is 170 and, therefore, 340 bits must pass (i.e., 2 * 170 bits) before the next determination is made as to whether a valid framing pattern is detected. Accordingly, valuable time is expended as the passage of those 2N bits occurs. Note also that a prior art example requiring more than three bits would require an additional delay of 1*N bit times for each additional bit beyond three bits before the next comparison is made.
Note also that FIG. 2 describes a single bit framer method, meaning, the method examines a first candidate single bit, a second candidate single bit, a third candidate single bit, and so forth. The prior art includes known multiple bit framers, meaning, the method of FIG. 2 is generally followed, but instead of a first candidate bit, a first group of successive candidate bits are collected, followed by a second group of successive candidates bits, followed by a third group of successive candidate bits, and so forth. The successive bits are then broken into candidate sets by taking corresponding bits from each group. For example, for a five bit framer evaluating three candidate bits, three groups of bits are collected and each group has five successive bits. Next, candidate bits are taken from corresponding locations within each group to form a set of candidate bits to be compared against the pattern at issue. Thereafter, the corresponding candidate bits in each set are examined to determine if they match the framing pattern. For the example above, the first bits of each group (e.g., the first bit of the first group, the first bit in the second group, and the first bit in the third group) are combined to form a first set of three candidate bits. Thus, these bits represent a sequence of spaced apart bits as in the instance of a single bit framer. This first set of candidate bits is then examined to determine whether they are a valid portion of a framing pattern. Simultaneously, the second bits of each group are likewise combined to form a second set of candidate bits and examined to determine whether they are a valid portion of a framing pattern, and so forth. Still further, the remaining three bits of the five bit groups are likewise accumulated with corresponding bits to determine whether any set of corresponding bits matches the framing pattern at issue. If no set matches the framing pattern at issue, the entire process repeats in the same manner as FIG. 2, but using sets of bits rather than single bits. Thus, each set, rather than each single bit, is examined in the multiple bit framer method. Thus, the multiple bit framer evaluates more possibilities at once in an effort to locate the framing pattern, but does so at the expense of additional hardware. Moreover, the prior art multiple bit framer suffers from the same drawback as the prior art single bit framer, namely, valuable time is expended as the process must completely repeat itself to collect a sufficient number of candidate bits to perform the necessary analysis.
It is therefore an object of the present invention to provide a method and apparatus for reducing the time necessary in locating a valid framing pattern.
It is a further object of the present invention to provide such a method and apparatus for reducing the necessary hardware in locating a valid framing pattern.
It is a further object of the present invention to provide such a method and apparatus for use in framer circuits using multiple consecutive slips.
It is a further object of the present invention to provide such a method and apparatus for use in either single or multiple bit framer circuits.
Still other objects and advantages of the present invention will become apparent to those of ordinary skill in the art having references to the following specification together with its drawings.